package leetcode.interviewClassics;

import leetcode.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/2 15:00
 */
public class pathSum2 {

    static List<List<Integer>> resultList = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(1, a, b);
        System.out.println(pathSum(c, 4));
    }

    static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum, new ArrayList<>());
        return resultList;
    }

    static void dfs(TreeNode node, int targetSum, List<Integer> nodeList) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            if (node.val == targetSum) {
                ArrayList<Integer> temp = new ArrayList<>(nodeList);
                temp.add(node.val);
                resultList.add(temp);
            }
        }
        nodeList.add(node.val);
        dfs(node.left, targetSum - node.val, nodeList);
        dfs(node.right, targetSum - node.val, nodeList);
        nodeList.remove(nodeList.size() - 1);
    }
}
